Der Quick Sort-Algorithmus ist ein Divide-and-Conquer-Sortieralgorithmus, der das Eingabearray rekursiv in immer kleinere Unterarrays aufteilt, bis jedes Unterarray nur noch ein Element enthält. Der Algorithmus ist schnell, effizient und in der Informatik weit verbreitet.
So funktioniert die Schnellsortierung:
1. Dividieren: Wählen Sie ein Pivot-Element aus dem Array (häufig das letzte Element).
2. Partition: Ordnen Sie das Array so um, dass sich alle Elemente, die kleiner als der Pivot sind, links vom Pivot befinden und alle Elemente, die größer als der Pivot sind, rechts. Das Pivot-Element befindet sich in seiner endgültigen Sortierposition.
3. Rekursion: Wiederholen Sie die beiden oben genannten Schritte für das linke und das rechte Subarray und zerlegen Sie sie rekursiv, bis jedes Subarray nur noch ein Element enthält.
Beispiel 1:
Betrachten Sie das Array [5, 3, 8, 2, 1, 4].
A. Teilen:Wählen Sie das letzte Element, 1, als Drehpunkt.
B. Partition:
- Ordnen Sie das Array neu an:[3, 2, 1, 5, 4, 8] (1 befindet sich an der sortierten Position).
C. Rekursion:
- Linkes Subarray:[3, 2, 1] (bereits sortiert)
- Rechtes Subarray:[5, 4, 8] (schnelle Sortierung rekursiv anwenden)
Nach der Anwendung der Schnellsortierung auf beide Unterarrays lautet das endgültige sortierte Array:[1, 2, 3, 4, 5, 8].
Beispiel 2:
Sortieren eines größeren Arrays
Betrachten Sie ein Array [7, 2, 9, 5, 3, 4, 1, 8, 6].
A. Teilen:Wählen Sie das letzte Element, 6, als Drehpunkt.
B. Partition:
- Ordnen Sie das Array neu an:[2, 5, 3, 4, 1, 7, 9, 6] (6 befindet sich in der sortierten Position).
C. Rekursion:
- Linkes Subarray:[2, 5, 3, 4, 1] (Schnellsortierung rekursiv anwenden)
- Rechtes Subarray:[7, 9] (bereits sortiert)
Nach Abschluss der rekursiven Aufrufe lautet das sortierte Array:[1, 2, 3, 4, 5, 6, 7, 8, 9].
Zeitkomplexität:
- Bester Fall:O(n log n)
- Durchschnittsfall:O(n log n)
- Worst-Case:O(n^2) (tritt auf, wenn das Array bereits sortiert oder umgekehrt sortiert ist)
Insgesamt bietet der Quick Sort-Algorithmus eine effiziente Sortierlösung mit einer guten durchschnittlichen Zeitkomplexität von O(n log n). Seine Einfachheit und Vielseitigkeit haben ihn zu einem beliebten Algorithmus zum Sortieren von Aufgaben in verschiedenen Programmiersprachen gemacht.
